class Solution {
public:
    static const int INF=0x3f3f3f3f;
    static const int MAXN=1e5+10;
    vector<vector<int>> divideArray(vector<int>& nums, int k) {

        vector<vector<int>> ret(nums.size()/3);
        sort(nums.begin(),nums.end());
        
        int minn[MAXN];
        for(int i=0;i<ret.size();++i){

            minn[i]=INF;
        }
        for(int i=0;i<nums.size();++i){

            int left=0,right=ret.size()-1;
            while(left<right){

                int mid=left+(right-left)/2;
                if(nums[i]-minn[mid]<=k && ret[mid].size()<3){

                    right=mid;
                }
                else{

                    left=mid+1;
                }
            }
            if(nums[i]-minn[left]>k ||ret[left].size()>=3){

                return vector<vector<int>>();
            }
            else{

                minn[left]=min(minn[left],nums[i]);
                ret[left].push_back(nums[i]);
            }
        }

        return ret;
    }
};
